package com.wtgroup.demo.leetcode.q146_LRU缓存机制;

import com.wtgroup.demo.common.util.InputParseUtil;

import java.lang.reflect.Method;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/4/28 15:17
 */
public class Q146_My1 {

    public static void main(String[] args) throws Exception {
        // String[] cmds = {/*"LRUCache", */"put", "put", "get", "put", "get", "put", "get", "get", "get"};
        // int[][] params = {
        //         /*{2}, */{1,1}, {2,2}, {1}, {3,3}, {2}, {4,4}, {1}, {3}, {4}
        // };
        List<String> cmds = InputParseUtil.parse("[\"get\",\"put\",\"get\",\"put\",\"put\",\"get\",\"get\"]"); // "LRUCache",
        List<List<Integer>> params = InputParseUtil.parse("[[2],[2,6],[1],[1,5],[1,2],[1],[2]]"); // [2],


        LRUCache lruCache = new LRUCache(2);
        for (int i = 0, cmdsLength = cmds.size(); i < cmdsLength; i++) {
            String cmd = cmds.get(i);
            List<Integer> param = params.get(i);
            Method method = null;
            Object res = null;
            if (cmd.equals("put")) {
                method = LRUCache.class.getDeclaredMethod(cmd, int.class, int.class);
                method.setAccessible(true);
                res = method.invoke(lruCache, param.get(0), param.get(1));
            } else {
                method = LRUCache.class.getDeclaredMethod(cmd, int.class);
                method.setAccessible(true);
                res = method.invoke(lruCache, param.get(0));
            }

            System.out.println(res);
        }


        // LRUCache lruCache = new LRUCache(2);
        // lruCache.put(2, 2);
        // lruCache.put(1, 1);
        // lruCache.put(3, 3);
        // lruCache.get(1); // 访问下1
        // System.out.println(lruCache);

        // HashMap<Object, Object> map = new HashMap<>();
        // map.put(2, 2);
        // map.put(1, 1);
        // map.put(3, 3);
        // System.out.println(map);
    }

    /**
     * 手写 Link + HashMap
     * 最少使用标记; 存储访问节点O(1)
     * */
    static class LRUCache {

        int cap = 16;
        Map<Integer, Node> map;
        Node head = null;
        Node tail = head;
        int size = 0;

        public LRUCache(int cap) {
            this.cap = cap;
            map = new HashMap<>(cap);
        }

        public int get(int key) {
            // 访问的 Node 移到队列尾部
            Node res = map.get(key);
            if (res != null) {
                moveToTail(res);
                return res.value;
            }

            return -1;
        }

        public void put(int key, int value) {

            // 新增的或更新的, 移动到队尾
            Node old = map.get(key);
            if (old == null) {
                Node node = new Node(key, value);
                map.put(key, node);
                addToTail(node);
                ++size;
                // ! 新增的才可能触发删除 oldest !
                if (size>cap) {
                    removeOldest();
                }
            } else {
                old.value = value;
                moveToTail(old);
            }
        }

        private void removeOldest() {
            // 删除最老的
            map.remove(head.key);
            head = head.next;
            if(head!=null) head.prev = null;
            --size;
        }

        // 移动或追加到末尾
        private void moveToTail(Node node) {
            // 双链表中删除
            removeNode(node);
            // 追加到尾部
            addToTail(node);
        }

        private void addToTail(Node node) {
            if (head==null) {
                head = node;
                tail = node;
                return;
            }

            tail.next = node;
            node.prev = tail;
            tail = node;
        }

        /**删除(unlink)逻辑参考 {@link LinkedHashMap#afterNodeRemoval(java.util.HashMap.Node)}*/
        public void removeNode(Node rm) {
            // 借鉴 LinkedHashMap#afterNodeRemoval 更简洁的实现
            Node prev = rm.prev;
            Node next =rm.next;
            rm.prev = rm.next = null;
            if (prev == null) {
                head = next;
            } else {
                prev.next = next;
            }
            if (next == null) {
                tail = prev;
            } else {
                next.prev = prev;
            }

            /*Node prev = rm.prev;
            Node next = rm.next;
            rm.prev = rm.next = null; // 重要, 避免循环
            if (prev!=null && next!=null) {
                prev.next = next;
                next.prev = prev;
            } else if (prev != null) { // next==null
                prev.next = null;
                tail = prev;
            } else if (next != null) { // prev==null
                head = next;
                next.prev = null;
            } else {
                head = null;
                tail = null;
            }*/
        }

        @Override
        public String toString() {
            Node c = head;
            String ret = "";
            while (c != null) {
                if (ret.length()>0) {
                    ret += ", ";
                }
                ret += (c.key + "->" + c.value);
                c = c.next;
            }

            return ret;
        }

        class Node {
            int key;
            int value;
            Node prev;
            Node next;

            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }
    }
}

